package com.lw.leetcode.tree.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 树状数组
 * 1409. 查询带键的排列
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/9 10:13
 */
public class ProcessQueries {

    public static void main(String[] args) {
        ProcessQueries test = new ProcessQueries();

        // [2,1,2,1]
//        int[] arr = {3, 1, 2, 1};
//        int m = 5;

        // [3,1,2,0]
//        int[] arr = {4, 1, 2, 2};
//        int m = 4;

        // [6,5,0,7,5]
        int[] arr = {7, 5, 5, 8, 3};
        int m = 8;

        int[] ints = test.processQueries(arr, m);
        System.out.println(Arrays.toString(ints));
    }

    private int[] arr;
    private int length;

    public int[] processQueries(int[] queries, int m) {
        int n = queries.length;
        this.length = m + n;
        this.arr = new int[length + 1];
        for (int i = n + 1; i <= length; i++) {
            add(i, 1);
        }
        int[] items = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            items[i] = n + i;
        }
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            int q = queries[i];
            int index = items[q];
            values[i] = get(index) - 1;
            add(index, -1);
            add(n - i, 1);
            items[q] = n - i;
        }
        return values;
    }

    private int get(int i) {
        int c = 0;
        while (i > 0) {
            c += arr[i];
            i = i - (-i & i);
        }
        return c;
    }

    private void add(int i, int v) {
        while (i <= length) {
            arr[i] += v;
            i = i + (-i & i);
        }
    }

}
